package com.zjw.algorithm.utils;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Utils {

    public static void main(String[] args) {
        System.out.println(toString(createFullBinaryTree(
                new int[]{1, 2, 3, 4, 6, 5, 7, 8, 9, 5, 6, 7, 8, 9, 1, 5, 1, 5, 7, 9, 6, 5, 3, 2, 4, 6, 3, 1, 2, 3, 4, 6, 5, 7, 8, 9, 5, 6, 7, 8, 9, 1, 5, 1, 5, 7, 9, 6, 5, 3, 2, 4, 6, 3,
                1, 2, 3, 4, 6, 5, 7, 8, 9, 5, 6, 7, 8, 9, 1, 5, 1, 5, 7, 9, 6, 5, 3, 2, 4, 6, 3, 1, 2, 3, 4, 6, 5, 7, 8, 9, 5, 6, 7, 8, 9, 1, 5, 1, 5, 7, 9, 6, 5, 3, 2, 4, 6, 3})));
    }


    public static String toString(TreeNode root) {
        if (root == null) {
            return "";
        }

        int height = getTreeHeight(root);

        StringBuilder builder = new StringBuilder();

        //{node,height,selfPositionInParentIsLeft,newLine}
        Queue<Object[]> queue = new ArrayDeque<>();

        queue.offer(new Object[]{root, height, false, true});

        while (!queue.isEmpty()) {
            Object[] poll = queue.poll();
            TreeNode node = (TreeNode) poll[0];
            int h = (int) poll[1];
            boolean isLeft = (boolean) poll[2];
            boolean newLine = (boolean) poll[3];

            long count = MathUtils.pow(2, h + 1);

            for (int i = 1; i <= count; i++) {
                if (i == count / 2 + 1) {
                    builder.append(node.val);
                } else {
                    builder.append(' ');
                }
            }

            if (newLine) {
                builder.append('\n');
            }

            if (node.left != null) {
                queue.offer(new Object[]{node.left, h - 1, true, false});
            }

            if (node.right != null) {
                queue.offer(new Object[]{node.right, h - 1, false, newLine && !isLeft});
            }
        }

        return builder.toString();
    }

    public static int getTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(getTreeHeight(root.left), getTreeHeight(root.right));
    }

    public static TreeNode createFullBinaryTree(int[] args) {
        if (args.length == 0) {
            return null;
        }

        TreeNode[] r = new TreeNode[args.length];

        for (int i = 0; i < args.length / 2; i++) {
            if (r[i] == null) {
                r[i] = new TreeNode(args[i]);
            }

            TreeNode node = r[i];
            if (2 * i + 1 < args.length) {
                //left
                node.left = new TreeNode(args[2 * i + 1]);
                r[2 * i + 1] = node.left;
            }

            if (2 * i + 2 < args.length) {
                //right
                node.right = new TreeNode(args[2 * i + 2]);
                r[2 * i + 2] = node.right;
            }
        }

        return r[0];
    }

    public static boolean isSubArray(int[] s, int[] t) {
        if (t.length > s.length) {
            return false;
        }

        if (t.length == 0) {
            return false;
        }

        int startValue = t[0];

        int startIndex = -1;

        for (int i = 0; i < s.length; i++) {
            if (s[i] == startValue) {
                startIndex = i;
                break;
            }
        }

        if (startIndex == -1) {
            return false;
        }

        for (int i = startIndex; i < s.length; i++) {
            if (i - startIndex >= t.length) {
                return true;
            }
            if (s[i] != t[i - startIndex]) {
                return false;
            }

            if (i + 1 >= s.length && i + 1 - startIndex >= t.length) {
                return true;
            }
        }
        return false;
    }


    public static int[] flatTwoDimensionArray(int[][] s) {
        int count = 0;
        for (int[] ints : s) {
            for (int anInt : ints) {
                count++;
            }
        }

        int[] r = new int[count];
        int index = 0;
        for (int[] ints : s) {
            for (int anInt : ints) {
                r[index++] = anInt;
            }
        }
        return r;
    }


    public static int[][] createTwoDimensionArrayFromOneDimension(int[] s, int width) {
        int[][] result = new int[s.length % width == 0 ? s.length / width : s.length / width + 1][];

        for (int i = 0; i < s.length; i++) {
            int j = i / width;

            if (result[j] == null) {
                //new
                result[j] = new int[width];
            }

            result[j][i % width] = s[i];
        }
        return result;
    }

    /**
     * @param data : "[[1,2,3,2,1,3],[312,32,13],[31,2,3,1,3,1]]"
     */
    public static int[][] createTwoDimensionArrayFromString(String data) {
        Matcher matcher = Pattern.compile("\\[[0-9,]*\\]").matcher(data);
        List<String> temp = new ArrayList<>();
        while (matcher.find()) {
            temp.add(matcher.group());
        }

        int[][] result = new int[temp.size()][];
        for (int i = 0; i < temp.size(); i++) {
            result[i] = createOneDimensionArrayFromString(temp.get(i));
        }
        return result;
    }

    /**
     * @param data : "[1,5,3,1]"
     */
    public static int[] createOneDimensionArrayFromString(String data) {
        String substring = data.substring(1, data.length() - 1);
        String[] split = substring.split(",");
        int[] result = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            result[i] = Integer.parseInt(split[i]);
        }
        return result;
    }


    public static String toString(ListNode head) {
        if (head == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();

        sb.append("[");

        sb.append(head.val);

        ListNode p = head.next;

        if (p != null) {
            sb.append(",");
        }

        while (p != null) {
            sb.append(p.val);
            if (p.next != null) {
                sb.append(",");
            }
            p = p.next;
        }
        sb.append("]");

        return sb.toString();
    }


    public static ListNode asNodeList(int[] arr) {
        if (arr.length == 0) {
            return null;
        }

        ListNode head = new ListNode(arr[0]);

        ListNode p = head;

        for (int i = 1; i < arr.length; i++) {
            p.next = new ListNode(arr[i]);

            p = p.next;
        }

        return head;
    }


    /**
     * 反转单链表
     * 空间复杂度 O(1)
     * 时间复杂度 O(n)
     */
    public static ListNode reverse(ListNode head) {
        //          滑动窗口算法
        //          |已逆转 |   |      未逆转       |
        //          [] <- []   [] -> [] -> [] -> []
        //                p1   p2    p3
        //
        // p1指向已经逆转的子链表头节点，p2指向未逆转子链表头节点
        ListNode p1 = head;
        ListNode p2 = p1 == null ? null : p1.next;

        if (p2 == null) {
            return p1;
        }
        //head next set null
        p1.next = null;
        while (p2 != null) {
            ListNode p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        return p1;
    }


    public static ListNode copy(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode copyHead = new ListNode(head.val);
        ListNode p1 = head.next;
        ListNode p2 = copyHead;
        while (p1 != null) {
            p2.next = new ListNode(p1.val);
            p1 = p1.next;
            p2 = p2.next;
        }
        return copyHead;
    }
}
